/* Author : 
 *    Daohang Shi 
 *    dshi7@wisc.edu 
 *    Fall  2013  
 *    */

#ifndef _CGR_H_
#define _CGR_H_

#include <bitset>
#include <iostream>
#include <cctype>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <limits>
#include <fstream>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <stdlib.h>
#include <set>
#include <stdint.h>
#include <ilcplex/cplex.h>

using namespace std;
#include <ext/hash_map>

using namespace __gnu_cxx;

//  first : net index
//  second : subnet index
typedef pair<uint32_t, uint32_t> TwoTerCoarseNetIdType;

typedef pair<int, int>  subnetIdType;

enum GridEdgeType { HORIZ, VERT, VIA };

enum GridNodeType { PRIMAL, STEINER };

struct NetTerminal
{
  public:
    int id;
    int   x, y, z;
    int   ne[6];
    int   nv[6];
    int   util;
    int   cap;
    int   absolute_overflow;    //  defined as util-cap;
    double  congestion_ratio;
    bool isDouble;
};

struct Segment { 
    int s;
    int t;
    string type;
    int length; //  num of edges in this segment
};

inline bool operator==(const NetTerminal &a, const NetTerminal &b)
{
  return a.x == b.x && a.y == b.y && a.z == b.z ;
}

inline bool operator!=(const NetTerminal &a, const NetTerminal &b)
{
  return a.x != b.x || a.y != b.y || a.z != b.z;
}

inline bool operator<(const NetTerminal &a, const NetTerminal &b)
{
  return    a.z<b.z || ( a.z==b.z && a.y<b.y ) || (a.z==b.z && a.y==b.y && a.x<b.x);
}

inline bool operator>(const NetTerminal &a, const NetTerminal &b)
{
  return    a.z>b.z || ( a.z==b.z && a.y>b.y ) || (a.z==b.z && a.y==b.y && a.x>b.x);
}

inline  int operator-(const NetTerminal &a, const NetTerminal &b) {
  return    abs(a.x-b.x) + abs(a.y-b.y) + abs(a.z-b.z);
}

struct TwoTerCoarseNet
{
  public:
    int   s, t;
    bool  is_congested;
    set<int>       edges;
};

inline bool operator==(const TwoTerCoarseNet &a, const TwoTerCoarseNet &b)
{
  return ( a.s==b.s && a.t==b.t && a.edges==b.edges );
}

inline bool operator!=(const TwoTerCoarseNet &a, const TwoTerCoarseNet &b)
{
  return ( a.s!=b.s || a.t!=b.t || a.edges!=b.edges );
}

inline bool operator<(const TwoTerCoarseNet &a, const TwoTerCoarseNet &b)
{
  return  ( a.s==b.s && a.t==b.t && a.edges<b.edges );
}

inline bool operator>(const TwoTerCoarseNet &a, const TwoTerCoarseNet &b)
{
  return  ( a.s==b.s && a.t==b.t && a.edges>b.edges );
}

typedef hash_map <uint32_t, uint32_t> GridEdgeSet;

class NetRoute 
{
  /* store the net route information in BFR */
  public:
    vector<TwoTerCoarseNet> subnets;
    set<int>  edges;

    NetRoute ( ) {}
    NetRoute ( vector<TwoTerCoarseNet> subnet_vector ) {
      subnets = subnet_vector;
      for ( vector<TwoTerCoarseNet>::iterator itr = subnets.begin(); itr != subnets.end(); itr++ )
        edges.insert ( (*itr).edges.begin(), (*itr).edges.end() ); 
    }
};

struct CoarseNet
{
  public:
    int       old_index;
    set<int>    terminal_pins;  //  read from input benchmark
    vector<Segment> sg;         //  read from global routing result
    vector< set<int> > crossing_points_on_segments;

    /* two set<int> designed for net modification */
    set<int>    inside_terminal_pins;
    set<int>    boundary_terminal_pins;
    vector<set<int> > disjoint_boundary_terminal_pins;  //  valid only if the modified net is not connected
    /* end */

    set<int>  edges;

    //
    set<int>  edges_backup; //  in case the error from linear relaxation
    //
    vector<TwoTerCoarseNet> subnets;  //  each subnet connect two terminal pins of the net
    set<int>  congested_edges;

    /* variables for candidate routes */

    /* TYPE 0 */
    vector< vector<TwoTerCoarseNet> >  candidate_subnets;
    vector< NetRoute> candidate_routes;
    /* end */
    vector<int> vxs;
    int route2DLength, route3DLength;

    set<int>    all_nodes;

//    GridEdgeSet         finalRoute;
//    vector<GridEdgeSet> finalRouteVector;

    int                 selected_route_index;
    vector<double>      decision_variable;
    int selected_route;   //  index of selected route in candidate route set(vector)
    vector<double>      lpSols;

    uint32_t selected;
    bool changed;

};

class GridEdge
{
  public:
    int         id;
    int         srcPoint, snkPoint;
    int         layer;
    int         cap;
    string      type;

    int         blk;    //  number of blocked routing tracks
    int         elr;    //  estimation for local routing    
    int         util;   //  demands of global routing
    int         virtual_util;   //  demands of global routing
    double      virtual_util_fp;
    int         absolute_overflow;  //  util - cap

    double      congestion_ratio;     //  congestion ratio
    double      pi;
    double      weight;      //  edge weight

    set<int>    nets_passing_through;
    double      histVal;
    double      te;
    double      oe,ds;

    //    all the two-terminal nets passing through this edge
    vector<subnetIdType> subnets_passing_through;
    vector<int>   related_nets;   //  store the old indexes
};

class SortNets
{
  const vector<CoarseNet> &nets;
public:
  SortNets(const vector<CoarseNet> &n): nets(n) {}

  bool operator()(const TwoTerCoarseNetIdType &a, const TwoTerCoarseNetIdType &b) const;
};

class GridBox
{
  public:
    int x0, y0;     //  index of lower-left point
    int dx, dy;
    
    double  average_absolute_overflow;
    bool    defined;

    int util;  
    int cap;
    int blk;

    int num_bad_edges;
    double  congestion_ratio;

    double  threshold;  //  smallest congestion ratio among the top 20%

    set<int>  congested_edges;

    GridBox():  x0(-1), y0(-1), dx(-1), dy(-1), defined(false)  {}

    void    set_values ( int llx, int lly, int width, int height )  {
      x0=llx; y0=lly; dx=width; dy=height;
      defined = true;
    }

    void  printBox () {
      cout << "Box from ("<<x0<<","<<y0<<") to ("
        << x0+dx-1<<"," << y0+dy-1 << ")\t" << dx << "x" << dy << endl;
    }
};

class CGR
{
  public:
    // benchmark stats
    int xGridNetTerminals, yGridNetTerminals, numLayers;
    int fullGridX, fullGridY;
    int minX, minY, tileWidth, tileHeight, halfWidth, halfHeight;

    bool considerDual;
    bool  isExpanded;   //  flag. initial as 'false' but turn 'true' as soon as starting CPLEX

    // data structures
    vector<uint16_t> vertCaps, horizCaps, mws, mss, viaSpacings;

    int xyzToGridNetTerminalId  ( int x, int y, int z );

    uint32_t edgeCount2D;
    uint32_t edgeCount3D;

    vector<CoarseNet> nets;         // nets[i] contains routes, plSols, finalRouteVector, selected, etc.
    map<int, int>   map_from_net_old_index_to_idnex_in_nets;  //  key is the old index in GR file and value is the index in net vector
    map<int, int>   map_from_net_old_index_to_index_in_bnets;  //  key is the old index in GR file and value is the index in net vector
    vector<int>         lambda;
    GridBox             bounding_box_to_solve;
    vector<GridBox>     bounding_boxes;
    vector<pair<int,GridBox> >  bounding_boxes_to_fix;
    vector<pair<GridBox, double> >  boxes_to_rank;  //  rank boxes in terms of ACE(20%)
    vector <GridEdge>           E;
    vector <NetTerminal>        V;
    //  V_2d, E_2d are used for generating congestion map
    vector <NetTerminal>  V_2d;
    vector <GridEdge>     E_2d;

    vector <int>          j_star;

    vector<GridBox> bounding_boxes_to_solve; 

    /* The following data structure are transferred from class GridBox to class CGR */
    vector<CoarseNet> bnets;
    vector<int> modified_net_type;
    vector<int> E_id;

    map<int,int>  map_from_edge_id_to_index_in_E_id;
    vector<pair<int, double> > congested_edges;

    map<int, set<int> >   edge_util_map;  //  key is edge id; value is all the net id passing throught the edge
    map<int, int>   subnet_old_index_map;    //  key is old index; value is index in box.bnets

    set<subnetIdType>   subnets_to_expand;

    int total_overflow;
    /* end */

    //  store the indexes of vxs and edges in the box

    int     x_var_size;

    vector<double> mj;
    vector<double> bj;
    double  tcr1, tcr2, tcr3;
    int jsize;

    double  TCR;

    //  performance optimization
    set<int>    all_the_congested_edges;
    //  end

    //  added on NOV 6
    vector<int> mini_net_id;
    vector<bool>  expand_mini_net_id;
    //  end

    //  added on NOV 11
    vector<pair<int, double> >  edge_CR;
    set<int>  top20;
    set<int>  unvisited_top20;
    vector<GridBox>   boxes;
    GridBox buildBoxFrom3DCongestedEdge ( int edge_id );
    double  critical_ratio;

    //  end

    //  added on NOV 17
    double  threshold_congestion_ratio;   //  the threshold value which determines if it is considered as "problematic edge"
    int starting_index;   //  the static variable in function "getNextEdgeToBuildBox" 
    double  A1, A2;
    set<int>  involved_hut_edges;
    //  end

    //  added on NOV 22
    map<int, set<int> > graph;
    set<int>  nodes;
    set<int>  unvisited_nodes;           //  used in dfs
    set<int>  unvisited_terminal_pins;  //  used in dfs
    int congested_edges_number_in_box;
    double  obj_bad;
    double  obj_good;
    double  slope;

    double  bdr1, bdr2, bdr3;

    bool    consider_continuous;
    //  end

    void init(void)
    {
      vertCaps.clear(); horizCaps.clear(); mws.clear();
      mss.clear(); viaSpacings.clear();
      xGridNetTerminals=0; yGridNetTerminals=0; numLayers=0;
      nets.clear();
    }

    void updateLPsols(void);

    void    genInitialGrid (void);
    void    initialRouting(void);
    void    readRouting(const char *inGRFile);

    void    insertEdgesFromSegments ( Segment &seg, CoarseNet &bnet ); 

    void    genModifiedNetsInBox (GridBox &box);
    CoarseNet genSingleModifiedNetInBox ( CoarseNet &net, GridBox &box );
    void    addModifiedSegmentInNet ( Segment &seg, CoarseNet &modified_net, GridBox &box );

    bool    isInBox ( int node_id, GridBox &box );
    bool    isInNetSegment ( int edge_id_number, Segment segment_in_net ); 
    bool    isInNet ( int edge_id_number, CoarseNet &net );
    bool    isConnected ( CoarseNet &net );

    int     getBoxes (void);
    int     getBoxes2 (void);
    int     getBoxes3 (void);
    void    getTotalOverFlow ( void );

    int     getNearestUnvisitedTerminalPin ( vector<int> nodes, map<int, set<int> > tree_in_adjacent_form, int starting_terminal_pin, set<int>  visited_nodes, set<int> &path );
    vector<int> getAdjacentNodes ( vector<int> nodes, set<int> edges, int u );
    int     getEdgeIdWithTwoEndingPoints ( int u, int v );

    void    findSteinerPoints ( CoarseNet &net );
    void    divideTwoTerNets ( CoarseNet &net );
    void    crossTwoSegments ( int i, int j, vector<Segment> segment_vector, vector<set<int> > &ref_crossing_points_on_segments );

    bool    compareDistBetweenTerminalPins ( const pair<int, int> &p1, const pair<int, int> &p2 );
    void    splitBoundaryTerminalPins ( CoarseNet &net );

    void    splitSegmentsWithCrossingPoints ( CoarseNet &net );

    void    netDecomposition ( CoarseNet &net );
    void    findCongestedEdges ( void );
    
    void    printSegmentEdges ( Segment seg );
    void    printSegmentVector ( vector<Segment> sg );
    void    printVertices ( vector<int> vxs );
    void    printEdgeSet ( set<int> edges ); 
    void    printEdgeWeightInSegment ( Segment segment ); 
    void    printEdge ( int edge_id );
    void    printEdge_2d ( int edge_id );
    void    printNode ( int node_id );
    void    printNode_2d ( int node_id );
    void    printIntVector ( vector<int> int_vector );
    void    printCrossingPointsOnSegments ( CoarseNet &net );
    void    printNet ( CoarseNet &net );
    void    printSubNet ( TwoTerCoarseNet &snet );

    int     getDeadEdgeNumberOfBox (void);
    void    countNumCongestedEdges (void);

    set<int>  getFlatSegment ( int s, int t );

    int     selfIncrementalBoundingBox ( GridBox &box );
    int     selfIncrementalBoundingBox2 ( GridBox &box );
    GridBox buildBoudingBoxFromCongestedEdge ( int edge_id );
    GridBox buildBoudingBoxFromCongestedEdge2 ( int edge_id );

    //  pre-process
    void    releaseDeadEdgeFromNet ( int edge_id, int net_id );

    vector<int> getEdgeVectorFromSegment ( Segment segment );
    vector<int> getNodeVectorFromSegment ( Segment segment );
    vector<int> getNodeVectorBetween ( int s, int t );

    bool    isOverlappingBoxes ( GridBox box1, GridBox box2 );
    int     removeEdgeRebundancyInNet ( CoarseNet &net ); 
    bool    isLegalRoute ( CoarseNet &net ); 
    bool    isOnBoundary ( int node, GridBox &box )
    {
      return  (V[node].x==box.x0 || V[node].x==box.x0+box.dx-1) && V[node].y>=box.y0 && V[node].y<box.y0+box.dy
      ||      (V[node].y==box.y0 || V[node].y==box.y0+box.dy-1) && V[node].x>=box.x0 && V[node].x<box.x0+box.dx ;
    }

    void    findNonOverlappingBoxes (int number_of_boxes);
    void    findNonOverlappingBoxes2 (int number_of_boxes);
    /* functions used in file "GEN_CANDIDATE_ROUTE.h" */
    bool    isLegalSubnet ( TwoTerCoarseNet &snet );
    string  getSubnetType ( TwoTerCoarseNet &snet );
    void    findUshapeCandidateRoute ( subnetIdType subnet_id );
    vector<NetRoute> getCompleteCandidateSet ( vector<vector<TwoTerCoarseNet> > candidate_subnets, int upper_bound_number ); 
    void    combineCandidateSubnetsToGenerateCandidateRoutes ( int M3 );
    void    findCompleteUShapeCandidateSubnetSetForFlatSegment ( GridBox &box, subnetIdType subnet_id, int M2 );
    void    findCompleteZShapeCandidateSubnetSetForCommonSegment ( GridBox &box, subnetIdType subnet_id, int M2 );
    double  computeSubnetEdgeWeight ( TwoTerCoarseNet &snet );
    double  computeNetRouteWeight ( NetRoute &net_route );
    void    initializeLoop (void);
    void    readyForNextIteration (GridBox &box);
    bool    isSubnetWithFlatEndingPoints ( TwoTerCoarseNet &snet );
    void    addNewCandidateRoutes ( int bnet_index, int upper_bound_number );
    void    refreshNetSegments (void);
    void    generateLongestSegments ( int index_in_nets ); 

    int     clearDeadEdges (void);
    bool    isLegalSegment ( Segment seg );
    /* end */

    /* functions that measures the performance metrics */
    double  getACE ( double y );
    vector<double>  getACE_vector ( vector<double>  &vy);
    int     getWCI ( double target_congestio_ratio ); 
    double  getGlobalObjVal ( void );
    double  getNetCongestioRatio ( CoarseNet &net );
    void    getInputGlobalRoutingInfo ( std::ofstream &stream_file );
    int     countBadEdges ( void );
    int     countBlockedEdges ( void );
    //  modified on NOV 4
    double  getACE20 ( GridBox &box );
    /* end */

    //  modified on NOV 6
    int     getNetHPWL ( CoarseNet &net );
    void    printNetHPWLDistribution ( void );
    set<int>  getBestRouteForFlatNet ( int s, int t );
    //  end

    //  modified on NOV 7
    void    genModifiedNetsInBox2 (GridBox &box);
    void    findNonOverlappingBoxes2 (void);
    void    checkCongestedEdgeNumberOfBox ( GridBox &box );
    int     getCongestedEdgeNumberOfBox ( GridBox &box );
    //  end

    //  modified on NOV 11
    double  getNewMetric (void);
    void  getTop20 ( void );

    pair<double,int>  getBoxAverageCongestionRatio ( GridBox &box );
    int     expandBox ( GridBox &box, pair<double,int> box_ave_cr );
    //  end
    //
    //  modified on NOV 12
    pair<GridBox, int> getNextBox ( int start );
    //  end
    int   replaceSegmentUsingSegmentIdNum ( CoarseNet &r_net_in_box, int segment_id_in_net_to_replace, Segment added_segment_with_smaller_weight ); 
  
    //  modified on NOV 16
    double  getEdgePenalty ( int edge_id );
    double  getBoxObjValue ( GridBox &box );
    int     expandBox2 ( GridBox &box );
    //  end
    //
    //  modified on NOV 17
    int     getNextEdgeToBuildBox (void);
    void    genModifiedNetsInBox3 (GridBox &box);
    set<int>  considered_nets;
    set<int>  small_considered_nets;
    bool    isInBoxNet ( CoarseNet &net, GridBox &box );
    void    readyForNextIteration2 ( GridBox &box );
    void    genCandidateRoutingForSimpleNet ( GridBox &box, CoarseNet &net, int M3 );
    void    genUShapeRoutings ( GridBox &box, CoarseNet &net, int s, int t, int M3 ); 
    void    genZShapeRoutings ( GridBox &box, CoarseNet &net, int s, int t, int M3 ); 

    void  selectBox(void);
    void    genModifiedNetsInBox4 (GridBox &box);
    //  end
    //
    //  modified on NOV 20
    void    readyForNextIteration3 ( GridBox &box );
    void    genCandidateRoute ( GridBox &box, int bnet_index, int added_routes );
    void    genCandidateRoutingForSimpleSubnet ( GridBox &box, TwoTerCoarseNetIdType subnet_id, int M3 );
    void    genUShapeRoutingsForSubnet ( GridBox &box, TwoTerCoarseNetIdType subnet_id, int M3 );
    void    genZShapeRoutingsForSubnet ( GridBox &box, TwoTerCoarseNetIdType subnet_id, int M3 );
    void    genCandidateRoutingForComplexSubnet ( GridBox &box, TwoTerCoarseNetIdType subnet_id, int M3 );
    void    genModifiedNetsInBox5 (GridBox &box);
    void    readyForNextIteration4 ( GridBox &box );
    void    genCandidateRoute2 ( GridBox &box, int bnet_index, int M3 );
    void    rerouteSingleCongestedEdge ( GridBox &box, int bnet_index, int edge_id );
    bool    isDanglingEdge ( CoarseNet &net, int edge_id );
    bool    isTerminalPin ( CoarseNet &bnet, int node );
    bool    detourPath ( CoarseNet &bnet, vector<int> node_path, double &detour_cost, set<int> &reroute );
    void    detourSingleEdge ( GridBox &box, int bnet_index, int edge_id );
    bool    isDanglingNode ( CoarseNet &bnet, int node, set<int> &reroute );
    bool    isValidRoute ( set<int> &terminal_pins );
    void    dfs ( int u );  //  graph has already been defined in this class
    void    genCandidateRoute3 ( GridBox &box, int bnet_index, int M3 );
    void    createBundles ( GridBox &box, int bnet_index, int edge_id );
    void    deleteEdgeFromGraph ( set<int> &terminal_pins, int edge_id );
    void    addEdgeToGraph ( int edge_id );
    void    buildGraph ( set<int> &pins, set<int> &edges );
    void    addSimplePattern ( int s, int t, int bnet_index );
    void    createPatternRoute ( GridBox &box, int bnet_index );
    void    genCandidateRoute4 ( GridBox &box, int bnet_index, int M3 );
    void    buildGridinBox ( GridBox &box );
    void    getCongestedNets ( std::ofstream &stream_file );
    void    getInputGlobalRoutingInfoInBox ( std::ofstream &stream_file );
    double  getACEInBox ( double y );
    int     getTWL ( void );
    double  getOBJInBox ( void );
    void    separateObjVal (void);
    void    computeBoxObjVal (void);
    void    recoverNets (void);
    //  end
    void  find_congested_area (void);
    void  gen_mst_order ( CoarseNet &net );
    void  write_initial_result (void);
    void  read_initial_result (void);
    int   return_edge_id ( int i, int j, int k, int type );
    void  refine_all_edges ( Segment seg, CoarseNet &net, CoarseNet &bnet );
    void  solve_ILP( void );
    void  retrace ( map<int,int> p, int s, int u, TwoTerCoarseNet &sn, CoarseNet &net );
    void  seg_router ( TwoTerCoarseNet &sn, CoarseNet &net );
    void  add_route ( CoarseNet &net );
    void  addSimplePatternRouting (GridBox &box, CoarseNet &snet, int upper_bound_number );
    void  genUShapeSubroute ( GridBox &box, CoarseNet &net, int s, int t );
    void  genZShapeSubroute ( GridBox &box, CoarseNet &net, int s, int t );
    vector<double>  getHist ( std::ofstream &stream_file );   //  get the histogram of edges in E_id
    double  getObjValInBox (void);
    double  getTHCR ( double y );
    double  getVirtualEdgePenalty ( int edge_id );
    void  recoverBox ( GridBox &box );
    double  getPenalty ( double y );
    //    
    bool    isCompletelyInBox ( CoarseNet &net );
    bool    isRouted ( CoarseNet &net );
    bool    isInSegment ( int vxs, Segment seg );

};
extern CGR cgr;

double cpuTime(void);

const double powMax = 1.e12;
const double powBase = 5.;
const double edgeBase = 2.;
const double viaFactor = 1;
const double epsilon = 1.;
const double historyIncrement = 1;

const string CGRversion = "1.0";

#endif
